package leedcode_path.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class N皇后 {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] qp=new char[n][n];
        for (char[] i:qp
             ) {
            Arrays.fill(i,'.');
        }
        backtracking(n,0,qp);
        return res;

    }
    public void backtracking(int n,int row,char[][] qp){
        if (n==row){
            res.add(liststring(qp));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (isValid1(n,row,i,qp)){
                qp[row][i]='Q';
                backtracking(n,row+1,qp);
                qp[row][i]='.';
            }
        }
    }

    private List<String> liststring(char[][] qp) {
        List<String> lis = new ArrayList<>();
        for (char[] i:qp
             ) {
            lis.add(String.copyValueOf(i));
        }
        return lis;
    }
    public  boolean isValid1(int n,int row,int cow,char[][] qp){
        for (int i = 0; i < row; i++) {
            if (qp[i][cow]=='Q'){
                return false;
            }
        }
        for (int i = row-1,j=cow-1; i >=0&&j>=0; i--,j--) {
            if (qp[i][j]=='Q'){
                return false;
            }
        }
        for (int i = row-1,j=cow+1; i >=0&&j<=n-1 ; i--,j++) {
            if (qp[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
}
